package ren.wxyz.algorithm.levenshtein;

/**
 * 编辑距离的实现算法
 * @author zxwang
 * @dateTime 2014年11月25日 下午2:06:19
 */
public class Test {

	/**
	 * 禁止外部被初始化
	 */
	private Test() {}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		String str1 = "GUMBO";
		String str2	= "GAMBOL";
		int lv = 0;
		long start = 0;
		long end = 0;
		
		start = System.currentTimeMillis();
		lv = multiLevenshtein(str1, str2);
		end = System.currentTimeMillis();
		System.out.println("lv=" + lv + ", time=" + (end - start));
	}

	/**
	 * 2乘的算法 <br>
	 * http://blog.jobbole.com/75496/<br>
	 * <table border="0" cellspacing="1" cellpadding="2" align="center">
	 * <tbody>
	 * <tr>
	 * <th bgcolor="#ffffcc">步骤</th>
	 * <th bgcolor="#ffffcc">说明</th>
	 * </tr>
	 * <tr>
	 * <td align="center" valign="top">1</td>
	 * <td>设置n为字符串s的长度。(“GUMBO”)<br>
	 * 设置m为字符串t的长度。(“GAMBOL”)<br>
	 * 如果n等于0，返回m并退出。<br>
	 * 如果m等于0，返回n并退出。<br>
	 * 构造两个向量v0[m+1] 和v1[m+1]，串联0..m之间所有的元素。</td>
	 * </tr>
	 * <tr>
	 * <td align="center" valign="top">2</td>
	 * <td>初始化 v0 to 0..m。</td>
	 * </tr>
	 * <tr>
	 * <td align="center" valign="top">3</td>
	 * <td>检查 s (i from 1 to n) 中的每个字符。</td>
	 * </tr>
	 * <tr>
	 * <td align="center" valign="top">4</td>
	 * <td>检查 t (j from 1 to m) 中的每个字符</td>
	 * </tr>
	 * <tr>
	 * <td align="center" valign="top">5</td>
	 * <td>如果 s[i] 等于 t[j]，则编辑代价为 0；<br>
	 * 如果 s[i] 不等于 t[j]，则编辑代价为1。</td>
	 * </tr>
	 * <tr>
	 * <td align="center" valign="top">6</td>
	 * <td>设置单元v1[j]为下面的最小值之一：<br>
	 * a、紧邻该单元上方+1：v1[j-1] + 1<br>
	 * b、紧邻该单元左侧+1：v0[j] + 1<br>
	 * c、该单元对角线上方和左侧+cost：v0[j-1] + cost</td>
	 * </tr>
	 * <tr>
	 * <td align="center" valign="top">7</td>
	 * <td>在完成迭代 (3, 4, 5, 6) 之后，v1[m]便是编辑距离的值。</td>
	 * </tr>
	 * </tbody>
	 * </table>
	 * 
	 * @param str1 字符串1
	 * @param str2 字符串2
	 * @return 编辑距离
	 */
	public static int multiLevenshtein(String str1, String str2) {
		if ((null == str1 || str1.length() == 0) && (null == str2 || str2.length() == 0)) {
			return 0;
		}
		// 直接判断出单极的情况
		if (str1.length() == 0) {
			return str2.length();
		}
		else if (str2.length() == 0) {
			return str1.length();
		}
		
		// 初始化变量
		char[] s = str1.toCharArray();
		char[] t = str2.toCharArray();
		int n = s.length;
		int m = t.length;
		int[] v0 = new int[m + 1];
		int[] v1 = new int[m + 1];
		// 初始化 v0 to 0..m
		for (int i = 0; i <= m; i++) {
			v0[i] = i;
		}
		
		// 编辑代价
		int cost = 0;
		
		// 计算
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cost = s[i-1] == t[j-1] ? 0 : 1;
				v1[j] = min(v1[j - 1] + 1, v0[j] + 1, v0[j - 1] + cost);
			}
		}
		
		return v1[m];
	}
	
	/**
	 * 找出最小值
	 * @param nums 整数
	 * @return 最小的整数
	 */
	private static int min(int... nums) {
		if (nums.length == 0) {
			throw new NullPointerException("没有数可以比较！");
		}
		if (nums.length == 1) {
			return nums[0];
		}
		if (nums.length == 2) {
			return nums[0] < nums[1] ? nums[0] : nums[1];
		}
		
		// 比较所有数据，找出最小值
		int min = nums[0];
		for (int num : nums) {
			if (min > num) {
				min = num;
			}
		}
		
		return min;
	}
}
